/************************************************************
 **  Ariel Morelli                                         **
 **  Carlos Pereira Lopes Filho                            **
 **  Gustavo Buzogany Eboli                                **
 **  Programacao Concorrente                               **
 **  Algoritmo Dijkstra em paralelo com MPI e OpenMP.      **
 **                                                        **
 ************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include "mpi.h"
#include <omp.h>

#define INFINITO 9000000
#define send_data_tag 2001
#define return_data_tag 2002
#define max 1010

/* Declaracao de matriz global. Apesar de ser global, cada thread precisa receber seus valores */
int matriz[1010][1010];

/* Encontra o adjacente minimo */
int minimo_adjacente(char *abertos, int origem, int *distancia, int num_nos){

    int menor = INFINITO;
    int i, j, menor_i=-1;

    /* Escolhe o vertice adjacente a origem, com a menor distancia */
    for(i=0;i<num_nos;i++){
        if(distancia[i]!=INFINITO && distancia[i]<menor && abertos[i]==1){
            menor = distancia[i];
            menor_i = i;
        }
    }

    /* Caso nao exista um vertice com estas caracteristicas, retorna (-1) */
    if(menor_i==-1){
        return -1;
    }
    
    /* Marca o vertice escolhido como fechado */
    abertos[i]=0;

    return menor_i+1;
}


/* Matriz inicial eh toda de valores INFINITO */
void inicializa_matriz(int num_nos){             

    int i, j;

    for(i=0;i<num_nos;i++){
        for(j=0;j<num_nos;j++){
            matriz[i][j]=INFINITO;
        }
    }
}

/* Retorna o maior elemento de um vetor */
int getMaior(int *vector, int start, int end){
    int i;
    int maior;
    maior=0;
    for(i=start;i<end;i++){
        if(vector[i]>maior)
            maior = vector[i];
    }
    return maior;
}

/* Retorna o menor elemento de um vetor */
int getMenor(int *vector, int start, int end){
    int i;
    int menor;
    menor=INFINITO;
    for(i=start;i<end;i++){
        if(vector[i]<menor)
            menor = vector[i];
    }
    return menor;
}

/* Verifica se ainda existem vertices abertos para serem analizados */
int existem_abertos(char *abertos, int num_nos){
    int i;
    for(i=0;i<num_nos;i++){
        if(abertos[i]==1)
            return 1;
    }
    return 0;
}

/* Todos os vertices se tornam 'abertos' */
char *abre_todos(char *abertos, int num_nos){
    int i;
    for(i=0;i<num_nos;i++){
        abertos[i]=1;
    }
    return abertos;
}


/* Funcao de Dijkstra retorna a maior distancia que a 'origem' possui... */
int Dijkstra(int origem, int num_nos){

    int i, u, v, aux, caso_teste=0;
    int *distancia = (int*) malloc (num_nos*sizeof(int));
    char *abertos;
    
    abertos = (char*)malloc(max*sizeof(char));
    abertos = abre_todos(abertos, num_nos);


    matriz[origem-1][origem-1]=0;

    for(i=0;i<num_nos;i++){
        distancia[i] = INFINITO; 
    }

    distancia[origem-1]=0;

    u=origem;

    while(existem_abertos(abertos, num_nos)){

        u = minimo_adjacente(abertos, u, distancia, num_nos);

        if(u==-1){
            return;
        }
        u--;

        for(v=0;v<num_nos;v++){
            if(matriz[v][u]<INFINITO){
                aux = distancia[u] + matriz[u][v];
                if(aux<distancia[v]){
                    distancia[v] = aux;
                }
            }
        }

        abertos[u]=0;
        u++; caso_teste++;
    }
    aux = getMaior(distancia, 0, num_nos);
    
    return aux;
}

void print_matriz(int num_nos){
    int i, j;
    printf("Matriz:\n");
    for(i=0;i<num_nos;i++){
        for(j=0;j<num_nos;j++){
            printf("%d ", matriz[i][j]);
        }
        printf("\n");
    }
    
}


int main(int argc, char **argv){

    MPI_Status status;
    int my_id, root_process, num_procs, an_id, sender ;
    int num_nos, num_arestas;
    int i, j, a, b, k, size;
    int media_nos, start, end, *maiores;
    int *maiores_threads;


    /* Vetor que armazena os maiores caminhos de cada vertice..
     * ex.: maiores[i] = distancia de i para seu vertice mais distante. */
    maiores = (int*)malloc(max*sizeof(int));

    MPI_Init(&argc, &argv);

    /* Processo principal, master */
    root_process = 0;

    MPI_Comm_rank(MPI_COMM_WORLD, &my_id);
    MPI_Comm_size(MPI_COMM_WORLD, &num_procs);
    
    /* Maior distancia que cada Thread retornou */
    maiores_threads = (int*)malloc(num_procs*sizeof(int));

    if(my_id == root_process) {

        scanf("%d %d", &num_nos, &num_arestas);

        media_nos = num_nos/num_procs;

        inicializa_matriz(num_nos);

        for(i=0;i<num_arestas;i++){
            scanf("%d %d %d", &a, &b, &size);
            matriz[a-1][b-1] = size;
            matriz[b-1][a-1] = size;
        }


        for(i=1;i<num_procs;i++){

            start = media_nos*i;
            end = start+media_nos;

            MPI_Send( &num_nos, 1 , MPI_INT,
                    i, send_data_tag, MPI_COMM_WORLD);
            MPI_Send( &start, 1 , MPI_INT,
                    i, send_data_tag, MPI_COMM_WORLD);
            MPI_Send( &end, 1 , MPI_INT,
                    i, send_data_tag, MPI_COMM_WORLD);
            for(j=0;j<num_nos;j++){
                MPI_Send( &matriz[j][0], num_nos , MPI_INT,
                        i, send_data_tag, MPI_COMM_WORLD);
            }

        }

        /* O processo 0 (master) tambem realiza sua parte do procesamento */
        #pragma omp parallel num_threads(NTHR)
        {
            #pragma omp for
            for(i=0;i<media_nos;i++){
                maiores[i] = Dijkstra(i+1, num_nos);
            }
        }

        maiores_threads[0] = getMenor(maiores, 0, media_nos);


    }

    if(my_id != root_process){

        MPI_Recv( &num_nos, 1, MPI_INT, 
                root_process, send_data_tag, MPI_COMM_WORLD, &status);
        MPI_Recv( &start, 1, MPI_INT, 
                root_process, send_data_tag, MPI_COMM_WORLD, &status);
        MPI_Recv( &end, 1, MPI_INT, 
                root_process, send_data_tag, MPI_COMM_WORLD, &status);
        for(k=0;k<num_nos;k++){
            MPI_Recv( &matriz[k][0], num_nos, MPI_INT, 
                    root_process, send_data_tag, MPI_COMM_WORLD, &status);
        }

        /* Cada Thread tem seu proprio vetor de maiores distancias */
        int *maiores_local = (int*)malloc((end-start)*sizeof(int));
        #pragma omp parallel num_threads(NTHR)
        {
            #pragma omp for
            for(i=0;i<end-start;i++){
                maiores_local[i] = Dijkstra(i+1+start, num_nos);
            }
        }

        int maior = getMenor(maiores_local, 0, (end-start));

        MPI_Send( &maior, 1, MPI_INT, root_process, 
                return_data_tag, MPI_COMM_WORLD);

    }

    /* Depois que todos os processos terminarem, eh hora de coletar os resultados */
    if(my_id == root_process){

        for(i=1;i<num_procs;i++){
            MPI_Recv( &a, 1, MPI_LONG, i,
                    return_data_tag, MPI_COMM_WORLD, &status); 
            sender = status.MPI_SOURCE;
            maiores_threads[i]=a;
        }

        printf("%d\n", getMenor(maiores_threads, 0, num_procs));

    }


    MPI_Finalize();

    return 0;

}
